package com.sicheng.lc.杂题.多路归并技巧之构造有序链表;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/12 14:57
 */
public class 丑数II {
    //https://leetcode.cn/problems/ugly-number-ii/

    private static final int N = 1690;
    static int[] dp = new int[N + 1];

    static {
        int i2 = 1, i3 = 1, i5 = 1;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;
            // 拓展结点取最小的
            int next = Math.min(next5, Math.min(next2, next3));
            dp[i] = next;
            // 逻辑上的有序链表指针后移，下次拓展结点
            if (next == next2)
                i2++;
            if (next == next3)
                i3++;
            if (next == next5)
                i5++;
        }
    }

    public int nthUglyNumber(int n) {
        if (n <= 6)
            return n;
        // dp[i] 是 第i个丑数
        return dp[n];
    }
}
